package 非比较排序;

public class CountSort {
    public static void sort(int[] arr){
        //先找到最大值
        int max=Integer.MIN_VALUE;
        for (int i : arr) max=Math.max(i,max);

        //声明计数数组
        int[] count=new int[max+1];
        for (int i : arr) count[i]++;

        //通过计数数组，将数组的索引值填充到原数组中
        int index=0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]>0){
                arr[index++]=i;
                count[i]--;
            }
        }
    }
}
